#include <stdio.h>
#include <stdlib.h>

//最短路径问题

//单源最短路径问题
/*
BFS算法

//求顶点u到其他顶点的最短路径
void BFS_MIN_Distance(Graph G, int u)
{
    // d[i]表示从u到i结点的最短路径
    for (i = 0; i < G.vexnum; ++i)
    {
        d[i] =∞;      //初始化路径长度
        path[i] = -1; //最短路径从哪个顶点过来
    }
    d[u] = 0;
    visited[u] = TRUE;
    EnQueue(Q, u);
    while (!isEmpty(Q)) // BFS算法主过程
    {
        DeQueue(Q, u); //队头元素u出队
        for (w = FirstNeighbor(G, u); W >= 0; w = NextNeighbor(G, u, w))
            if (!visited[w]) // w为u的尚未访问的邻接顶点
            {
                d[w] = d[u] + 1; //路径长度加1
                path[w] = u; //最短路径应从u到w
                visited[w] = TRUE; //设已访问标记
                EnQueue(Q, W); //顶点w入队
            } // if
    }         // while
}


Dijkstra算法
BFS缺陷，只能解决无权图
如果带权图中存在权值为负数的边，则Dijkstra算法可能失效

final[n]：标记个顶点是否已找到最短路径
dist[n] ：最短路径长度
path[n] ：路径上的前驱

1、循环遍历所有结点，找到还没确定最短路径，且dist最小的顶点Vi，令final[i]=true
2、检查所有邻接自Vi的顶点，若其final值为false，则更新dist和path信息
3、循环上述两个步骤


实例见图：Dijkstra.jpg
初始
final:   1   0   0   0   0
dist :   0   10  ∞   ∞   5
path :   -1  0   -1  -1  0 

final:   1   0   0   0   1
dist :   0   8   14  7   5
path :   -1  4   4   4   0 

final:   1   0   0   1   1
dist :   0   8   13  7   5
path :   -1  4   3   4   0 

final:   1   1   0   1   1
dist :   0   8   11  7   5
path :   -1  4   1   4   0 

v0 --> v2的最短带权路径
v2 <-- v1 <-- v4 <-- v0

*/

//各顶点之间的最短路径
/*
Floyd算法
可以解决代负权值的图

见图 Floyd.jpg


*/

int main()
{
    printf("\n\n========================================================================\n\n");

    printf("\n\n========================================================================\n\n");
    return 0;
}